#include <cstdio>

struct ListNode {
    int val; // 当前节点的值
    ListNode* next; // 后继指针
    ListNode* prev; // 前驱指针

    ListNode(int val) :
        val(val),
        next(NULL),
        prev(NULL) {}
};


struct List {
    //头节点
    ListNode* head;
    //尾节点
    ListNode* tail;
    //链表大小
    int size;

    //构造方法
    List() : head(NULL), tail(NULL), size(0) {}


    //添加节点
    void Add(int val) {
        ListNode* newNode = new ListNode(val);
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        }
        else {
            tail->next = newNode;
            newNode->prev = tail; //设置新节点的前驱指针
            tail = newNode;
        }
        size++;
    }

    //打印
    void Print() {
        ListNode* cur = head;
        while (cur != NULL) {
            printf("值=[%d],地址=[%p],下一个地址=[%p]\n",
                cur->val, cur, cur->next);
            cur = cur->next;
        }
    }

    //查找
    ListNode* Find(int val) {
        ListNode* cur = head;
        while (cur != NULL) {
            if (cur->val == val) {
                return cur;
            }
            cur = cur->next;
        }
        return NULL; //未找到
    }

    //删除
    void Delete(int val) {
        //链表为空
        if (head == NULL) return;

        //如果只有一个节点
        if (head->next == NULL) {
            if (head->val == val) {
                delete head;
                head = NULL;
                tail = NULL;
                size--;
            }
            return;
        }

        //当前节点
        ListNode* cur = head;
        //前一个节点
        ListNode* prev = NULL;

        while (cur != NULL) {
            if (cur->val == val) {
                //如果是头节点
                if (prev == NULL) {
                    head = cur->next;
                }
                //如果是尾节点
                else if (cur->next == NULL) {
                    tail = prev;
                    prev->next = NULL;
                }
                //如果是中间节点
                else {
                    prev->next = cur->next;
                }
                delete cur; //释放内存
                //更新链表大小
                size--;
                return;
            }
            //更新前一个节点和当前节点
            prev = cur;
            cur = cur->next;
        }
    }

    //获取链表大小
    int GetSize() const {
        return size;
    }


    //析构函数
    ~List() {
        ListNode* cur = head;
        while (cur != NULL) {
            ListNode* nextNode = cur->next;
            delete cur; //释放当前节点内存
            cur = nextNode; //移动到下一个节点
        }
        head = NULL; //清空头节点
        tail = NULL; //清空尾节点
        size = 0; //重置大小
    }

};

/**
 * 双向链表
 */
int main(){



    return 0;
}